package me.wangshier.leetcode.medium;

import java.util.HashSet;
import java.util.Set;

/**
 * 17. 小M的数组变换
 *
 * @Author: tongqianwen
 * @Date: 2025/3/10
 */
public class ArrayTransform {
    // 获取一个数的所有素因子,用Hashset存储，避免重复
    private static Set<Integer> getPrimeFactors(int x) {
        Set<Integer> primeFactors = new HashSet<>();
        for (int i = 2; i * i <= x; i++) {
            while (x % i == 0) {
                primeFactors.add(i);
                x /= i;
            }
        }
        if (x > 1) {
            primeFactors.add(x);
        }
        return primeFactors;
    }

    public static String solution(int n, int[] a) {
        // 使用一个HashSet存储所有元素的素因子集合
        Set<Integer> factorSets = new HashSet<>();

        for (int num : a) {
            Set<Integer> factors = getPrimeFactors(num);
            factorSets.addAll(factors);
        }
        // 如果factorSets集合的大小超过 a数组个数，则说明无法通过转移素因子使每个数的素因子个数小于等于1
        return factorSets.size() <= n ? "Yes" : "No";
    }

    public static void main(String[] args) {
        System.out.println(solution(4, new int[]{1, 2, 3, 4}).equals("Yes"));
        System.out.println(solution(2, new int[]{10, 12}).equals("No"));
        System.out.println(solution(3, new int[]{6, 9, 15}).equals("Yes"));
    }
}